package Tree.binaryTree;

import java.util.*;

public class binaryTreeSolution01 {
    //二叉树的深度遍历
    //前序/中序/后序遍历  --用递归 或者栈


    /**
     * 前序遍历二叉树 DLR
     * @param root
     * @param result
     */

    public void preOrder(TreeNode root, List<Integer> result) {
        if(root == null) {
            return;
        }
        result.add(root.val);
        preOrder(root.left, result);
        preOrder(root.right, result);
    }
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preOrder(root, result);
        return result;
    }

    //用非递归实现前序遍历 DLR
    // 前序遍历顺序：中-左-右，入栈顺序：中-右-左

    /**
     * 因为前序遍历的顺序是中左右，先访问的元素是中间节点，
     * 要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，
     * 因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal_1(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if(root == null) {
            return result;
        }
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            //先放右左 --出来才能是左右
            if(node.right != null) {
                stack.push(node.right);
            }
            if(node.left != null) {
                stack.push(node.left);
            }
        }
        return result;
    }


    /**
     * 中序遍历二叉树 LDR
     * @param root
     * @param result
     */
    public void inOrder(TreeNode root, List<Integer> result) {
        if(root == null) {
            return;
        }
        inOrder(root.left, result);
        result.add(root.val);
        inOrder(root.right, result);
    }

    //用非递归实现中序遍历 LDR
    // 中序遍历顺序: 左-中-右 入栈顺序： 左-右
    //在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。
    public List<Integer> inorderTraversal_1(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if(root == null) {
            return result;
        }
        //执行当前处理的元素
        TreeNode cur  = root;
        if(cur != null ||  !stack.isEmpty()) {
            if(cur != null) {
                stack.push(cur);
                //依次让左子树入栈
                cur = cur.left;
            } else {
                cur = stack.pop();
                result.add(cur.val);
                cur = cur.right;
            }
        }
        return result;
    }

    /**
     * 后序遍历二叉树 LRD
     * @param root
     * @param result
     */

    public void postOrder(TreeNode root, List<Integer> result) {
        if(root == null) {
            return;
        }
        postOrder(root.left, result);
        postOrder(root.right, result);
        result.add(root.val);
    }

    //用非递归实现后序遍历 LRD

    //可以解决前线的非递归，DRL 然后再反转，变成LRD
    public List<Integer> postorderTraversal_1(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if(root == null) {
            return result;
        }
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            //先放左右，出来才能按右左处理
            if(node.left != null) {
                stack.push(node.left);
            }
            if(node.right != null) {
                stack.push(node.right);
            }
        }
        // DRL 反转一些就是LRD 后续遍历
        Collections.reverse(result);
        return result;
    }

    /**
     * 二叉树的层次遍历
     * 力扣102 - 从上到下按层打印二叉树，每一层一个List -medium
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> resList = new ArrayList<List<Integer>>();
        checkFun02(root,resList);
        return resList;
    }
    //BFS--迭代方式--借助队列
    public void checkFun02(TreeNode node,List<List<Integer>> resList) {
        if (node == null) return;
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.offer(node);

        while (!que.isEmpty()) {
            List<Integer> itemList = new ArrayList<Integer>();
            int len = que.size(); //这个len就是当前要处理的这一层的元素个数，也就是控制每一层要弹出几个元素

            while (len > 0) {
                TreeNode tmpNode = que.poll();
                itemList.add(tmpNode.val);

                if (tmpNode.left != null) que.offer(tmpNode.left);
                if (tmpNode.right != null) que.offer(tmpNode.right); //如果根节点左右孩子都有，那么下一次len就是2了，控制只弹2个元素再List里面
                len--;
            }

            resList.add(itemList);
        }
    }


    /**
     * 二叉树的层次遍历 II --返回其节点值 自底向上的层序遍历 。
     * @param root
     * @return
     * 可以用链表实现数组，头插法收集数据
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        // 利用链表可以进行 O(1) 头部插入, 这样最后答案不需要再反转
        LinkedList<List<Integer>> resList = new LinkedList<>();
       if (root == null) return resList;
       Queue<TreeNode> que = new LinkedList<TreeNode>();
       que.offer(root);
       while (!que.isEmpty()) {
           List<Integer> itemList = new ArrayList<Integer>();
           int len = que.size();
           while (len > 0) {
               TreeNode tmpNode = que.poll();
               itemList.add(tmpNode.val);
               if (tmpNode.left != null) que.offer(tmpNode.left);
               if (tmpNode.right != null) que.offer(tmpNode.right);
               len--;
           }
           resList.addFirst(itemList);
       }
       return resList;
    }

}
